import re


def solution(m: int, s: str) -> int:
    # 统计各种情况的数量
    s, nUCC = re.subn(r"UCC", "AAA", s)
    s, nUC = re.subn(r"UC", "BB", s)
    s, nCC = re.subn(r"CC", "DD", s)
    nsg = len(s) - 3 * nUCC - 2 * nUC - 2 * nCC

    # 更新结果和步数
    res = nUCC
    if m > nUC + nCC:
        res += nUC + nCC
        m -= nUC + nCC
        if m // 2 < nsg:
            res += m // 2
        else:
            res += nsg
            m -= 2 * nsg
            res += m // 3
    else:
        res += m
    return res


if __name__ == '__main__':
    print(solution(m=3, s="UCUUCCCCC") == 3)
    print(solution(m=6, s="U") == 2)
    print(solution(m=2, s="UCCUUU") == 2)

